import java.util.Scanner;

public class Demo02 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//物品个数
        int m = sc.nextInt();//背包容量

        int[] w = new int[n];//物品的重量
        int[] v = new int[n];//物品的价值
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                //j背包容量
                //w[i-1]当前物品的重量
                if (j >= w[i - 1]) {//如果背包容量放得下当前物品
                    //v[i - 1]当前物品的价值
                    //w[i - 1]当前物品的重量
                    //dp[i][j - w[i - 1]]背包剩余容量的最优价值
                    //v[i - 1] + dp[i - 1][j - w[i - 1]] 如果拿当前物品的情况下获得的价值
                    //dp[i - 1][j]不拿当前物品的最优价值
                    dp[i][j] = Math.max(v[i - 1] + dp[i - 1][j - w[i - 1]], dp[i - 1][j]);
                } else {//如果背包容量放不下当前物品
                    //放不下的话就直接拿上个物品的最优价值
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}
